1. Technical Field
This invention generally relates to computer system resource management and more specifically relates to memory management in a multi-threaded programming environment.
2. Background Art
The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices, and computer systems may be found in many different settings. Computer systems typically include a combination of hardware (e.g., semiconductors, circuit boards, etc.) and software (e.g., computer programs). As advances in semiconductor processing and computer architecture push the performance of the computer hardware higher, more sophisticated computer software has evolved to take advantage of the higher performance of the hardware, resulting in computer systems today that are much more powerful than just a few years ago.
Computer systems typically include operating system software that controls the basic function of the computer, and one or more software application programs that run under the control of the operating system to perform desired tasks. For example, a typical IBM Personal Computer may run the OS/2 operating system, and under the control of the OS/2 operating system, a user may execute an application program, such as a word processor. As the capabilities of computers have increased, the application programs designed for high performance computer systems have become extremely powerful.
As a computer system is utilized to accomplish the various tasks for which it was designed, it uses an electronic memory storage area in order to perform the necessary calculations and manipulations associated with the processes at hand. The xe2x80x9cstackxe2x80x9d is a dedicated portion of the computer system""s memory storage area used by the computer system to store the state of the computer system, to pass variables between functions, and to store return addresses so that the system can return to its original location before function calls. Thus, the stack serves as a temporary storage location where the computer can place interim information while performing various processing operations. As a part of the processing associated with the normal operations of the computer system, the computer system will issue xe2x80x9cfunction callsxe2x80x9d for various procedures. Whenever the system calls a function as part of accomplishing a task, the current state of the computer (if needed), a return address, and variables being passed to and from the function are placed into an area of the stack known as a xe2x80x9cstack framexe2x80x9d and placed onto the stack for use by the system.
Because computer systems are designed in a multitude of different ways, stacks are also implemented in several ways. Portions of an operating system, which control most computer systems these days, may use more than one stack. Furthermore, stacks can be implemented in a fixed size, wherein stacks can only grow so large, or stacks can be implemented in an xe2x80x9cinfinitexe2x80x9d size, wherein stacks can use hard drive or other space to grow until the hard drive or other space is completely full. If the size of the stack is fixed, care must be exercised so as not to exceed the boundaries of the stack. If more stack frames are placed onto the stack than can be accommodated within the preestablished limits of the stack, then the stack xe2x80x9coverflowsxe2x80x9d and the entire system can crash as the instructions stored on the stack overwrite other areas of the computer system""s memory storage area. This type of memory error will commonly cause loss of data and other significant problems. In addition, some systems will completely and irretrievable lock if the stack is overflowed. Most systems will, at a minimum, generate stack exceptions. Even those systems that have an infinite stack will suffer a performance hit if the stack grows too large because most of the stack will be on the hard disk, and hard disks are substantially slower than memory.
As a general rule, each different function call, processed during the computer""s normal operation, will generate a stack frame that will be placed on the stack for eventual removal by the computer system. One function call generally creates one stack frame on the stack and 10 function calls will generate 10 stack frames on the stack. If too many function calls are made and too many stack frames are generated, the stack frames can exceed the logical limits of the stack boundaries and overrun the limits of the stack portion of the memory as described above. Furthermore, even if the stack size is not fixed, the system will suffer a serious performance hit because the stack will be paged into and out of disk memory.
These stack overflow errors are possible when an asynchronous function, particularly a subsystem function, completes its task xe2x80x9csynchronously.xe2x80x9d In this scenario, a system would ask a subsystem function to perform a task by calling the function and handing it a variable that indicates what task is to be performed. The system will also generally pass a callback entry point (the address of a callback function) to the subsystem function. The callback entry point acts as a notice to the subsystem that the subsystem needs to call the system back when the task has been completed, and that the subsystem should call a particular callback function that is pointed to by the callback entry point. A stack frame is placed on the stack with the call to the subsystem function. The subsystem knows that it can immediately complete its task, and it does so. This completion is termed xe2x80x9csynchronousxe2x80x9d because the task was completed in the same computer state. The subsystem may call other sub-functions or subsystems that help it complete the task. Each of these sub-functions will generally result in stack frames being placed on the stack. Some of these stack frames may still be on the stack when the subsystem function calls back the system by calling the callback function. This is particularly true if a sub-function of the subsystem function performs the call to the callback function, because the call to the sub-function will generate another stack frame. The callback function causes yet another stack frame to be placed on the stack.
Therein lies the potential stack problem. There are many stack frames on the stack, and the stack has not had a chance to xe2x80x9cunwind.xe2x80x9d Unwinding, also called unwrapping, a stack is basically the process of allowing the system to xe2x80x9ccatch upxe2x80x9d to the multitude of stack frames on the stack. Functions are returned from and each return unwinds or unwraps the stack by removing the stack frame, associated with the function being return from, off the stack. For instance, if no more functions are called at this point in the scenario, normal processing would incur a return from the callback function, returns from all of the sub-functions called by the subsystem, and a return from the subsystem function. The stack would then be at its starting point. The problem arises when these multiple frames are on the stack and more calls to similar subsystems or the same subsystem occur. Or, if a function is looping through a repetitive series of similar asynchronous function calls that complete in a synchronous fashion, it is quite possible that the accumulated callback functions can quickly cause the stack to overflow. This looping causes a problem because each call to an asynchronous function that completes synchronously causes more stack frames to be placed on the stack, with no opportunity to unwind the stack. This looping can happen, for example, if large amounts of data are being moved from a disk drive to memory.
There are several possible solutions to this stack dilemma known to those skilled in the art. For example, it is possible to have the system treat every function call in the same manner and wait for the task to be completed before processing the next function call. While ensuring that the stack will not overflow, this approach is extremely inefficient from a processing point of view. Alternatively, it is possible to create an xe2x80x9cinfinite stack,xe2x80x9d where the size of the stack can grow as large as necessary. As explained previously, this solution is also inefficient because system performance will deteriorate as the size of the stack increases. At present, a system must either operate without adequate stack overflow protection or operate with inefficient processing restraints which are counterproductive in today""s demanding computer-based business environment.
Therefore, there exists a need for a more acceptable stack overflow protection system. Without an improved mechanism for monitoring and managing the stack to prevent undesirable overflows, systems will continue to suffer from artificial processing limitations or unnecessary exposure to stack overflows and the concomitant system crashes that accompany this situation.
According to the preferred embodiments of the present invention, a stack unwinding mechanism is provided that reduces stack overflow problems by determining if an asynchronous function completed synchronously and unwinding the stack if the function did complete synchronously. The stack unwinding mechanism then completes the client""s processing of the asynchronous function""s task after the stack has been unwound. This allows client processing to take place when there is little chance of stack overflow or overgrowth. If the asynchronous function will complete asynchronously, the stack unwinding mechanism allows processing to continue normally because there is little chance for stack overflow in this situation. By providing stack management for asynchronous function calls that complete synchronously and by unwinding the stack, the stack unwinding mechanism reduces the chances of stack overflow from synchronous completion of asynchronous functions. The various embodiments of the present invention disclosed herein are especially well-suited to embedded processor environments.